class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat)
    {
        int n = mat.size();
        int m = mat[0].size();
        for (int i = n - 1; i >= 0; i--)
        {
            vector<int> tmp;
            for (int j = i, k = 0; j < n && k < m; k++, j++)
                tmp.push_back(mat[j][k]);
            ranges::sort(tmp);
            for (int j = i, k = 0; j < n && k < m; k++, j++)
                mat[j][k] = tmp[k];
        }
        for (int i = 1; i < m; i++)
        {
            vector<int> tmp;
            for (int j = 0, k = i; j < n && k < m; j++, k++)
                tmp.push_back(mat[j][k]);
            ranges::sort(tmp);
            for (int j = 0, k = i; j < n && k < m; j++, k++)
                mat[j][k] = tmp[j];
        }
        return mat;
    }
};